\section{Monomial Orders}

A Gröbner basis always pertains to a particular order on monomials. Let us
therefore introduce the most fundamental ones.

Before we actually define a monomial order, let us start with a concise
discussion about binary relations so that it is convenient to prove that certain
orders are in fact monomial orders.

\begin{df}
  Let $S$ be a non-empty set. A \textbf{binary relation} on $S$ is a subset $r$
  of $S \times S$. The relation $\Delta\!\left( S \right) = \set*{\left( a, a \right)~|~a
    \in S}$ is the \textbf{diagonal} of $S$.
\end{df}

We will use only binary relations in our work and so we will refer to them
simply as relations. In order to simplify the notation, we will also employ
infix notation to denote that two elements are in a relation, i.e., if $r$ is a
binary relation on $S$ and $a, b \in S$, then $a~r~b$ will mean $\left( a, b
\right) \in r$.

\begin{df}
  \sloppy Let $r$ and $s$ be relations on $S$. The relation $r^{-1} =
  \set*{\left( a, b \right) | \left( b, a \right) \in r}$ is the \textbf{inverse}
  of $r$. The \textbf{strict part} of $r$ is the relation $r_s = r \setminus r^{-1}$,
  and \[s \circ r = \set*{\left( a, c \right)~|\text{ there is } b \in S \text{ such
        that } \left( a, b \right) \in r \text{ and } \left( b, c \right) \in s}\]
  is the \textbf{product} of $r$ and $s$.
\end{df}

\begin{df}
  Let $r$ be a relation on $S$. Then $r$ is
  \begin{enumerate}[label=(\roman*)]
  % \item \textbf{reflexive} if $\Delta\!\left( S \right) \subseteq r$,
  \item \textbf{transitive} if $r \circ r \subseteq r$,
  \item \textbf{antisymmetric} if $r \cap r^{-1} \subseteq \Delta\!\left( S \right)$,
  \item \textbf{connex} if $r \cup r^{-1} = S \times S$,
  % \item a \textbf{partial order on} $S$ if $r$ is reflexive, transitive and
  %   antisymmetric,
  \item a \textbf{linear order on} $S$ if $r$ is transitive, antisymmetric and
    connex.
  \end{enumerate}
\end{df}

\begin{df}
  Let $r$ be a relation on $S$ with strict part $r_s$ and let $R \subseteq S$. An
  element $a \in R$ is \textbf{minimal} if there is no $b \in R$ such that
  $b~r_s~a$. A \textbf{strictly descending} (or \textbf{strictly decreasing})
  \textbf{sequence} in $S$ is an infinite sequence of elements $a_n \in S$ such
  that $a_{n+1}~r_s~a_n$ for all $n \in \mathbb{N}$. The relation $r$ is
  \textbf{noetherian} if every non-empty subset $R$ of $S$ has a minimal
  element. The relation $r$ is a \textbf{well-order} on $S$ if it is a
  noetherian linear order on $S$.
\end{df}

A natural way to think about the strict part of a relation is to consider the
natural order on $\mathbb{N}$, which is a linear order, where for each $m, n \in
\mathbb{N}$; $m > n$ means $m \ge n$ and $m \ne n$. The symbol $>$ denotes the
strict part of the relation $\ge$. We will also denote our orders on monomials by
$\succeq$, the inverse will be $\preceq$ and the strict parts will be denoted
$\succ$ and $\prec$.

We will denote by $\mathcal{M}\!\left( x_1, \ldots, x_n \right)$, or simply
$\mathcal{M}$, the set of all monomials in the indeterminates $x_1, \ldots, x_n$. It
turns out that $\mathcal{M}$ forms an Abelian monoid under natural
multiplication where we add corresponding exponents of the indeterminates. The
multiplicative identity is the monomial 1. Note that we can associate any
monomial $x^\alpha \in \mathcal{M}\!\left( x_1, \ldots, x_n \right)$ with its $n$-tuple of
exponents $\alpha = \left(\alpha_1, \ldots, \alpha_n\right) \in \mathbb{N}_0^n$ in a one-to-one
fashion. Thus, we can use the sets $\mathcal{M}$ and $\mathbb{N}_0^n$
interchangeably.

\begin{lm}
  \label{order_lm}
  A linear order $\ge$ on $S$ is a well-order if and only if there is no
  strictly descending sequence in $S$.
\end{lm}

\begin{p}
  Let us turn the lemma into its contrapositive form: $\ge$ is not a well-order if
  and only if there is a strictly descending sequence in $S$; and prove this
  version of the lemma.

  \begin{itemize}
  \item[$\implies$] Suppose $\ge$ is not a well-order. Then there is a non-empty
    subset $R \subseteq S$ that has no minimal element. We can choose $a \in R$ and
    since $a$ is not the minimal element, we can choose again $b \in R$ such that
    $a > b$, which leads to a strictly descending sequence.

  \item[$\impliedby$] Suppose there is a strictly descending sequence in $S$.
    The elements of such a sequence form a non-empty subset $R$ of $S$ that has
    no minimal element. Hence, $\ge$ is not a well-order. \qedhere
  \end{itemize}
\end{p}

\begin{df}
  \label{monomial_order_df}
  A \textbf{monomial order} $\succeq$ is a well-order on $\mathcal{M}$, which
  satisfies the \textbf{property of respecting multiplication}: if $m_1 \succeq m_2$,
  then $n \cdot m_1 \succeq n \cdot m_2$ for all $m_1, m_2, n \in \mathcal{M}$.
\end{df}

The purpose of the property of respecting multiplication is that the relative
ordering of monomials in a polynomial does not change when we multiply the
polynomial by a monomial. Such behavior is necessary for the division algorithm
described in the next section.

\begin{df}[Lexicographic order]
  Let $x^\alpha, x^\beta \in \mathcal{M}\!\left( x_1, \ldots, x_n \right)$ be monomials. We say
  $x^\alpha \succeq_{lex} x^\beta$ if $\alpha = \beta$ or if there is $1 \le i \le n$ such that $\alpha_j = \beta_j$
  for $1 \le j < i$ and $\alpha_i > \beta_i$.
\end{df}

Note that $\succ_{lex}$ compares the exponent $n$-tuples $\alpha, \beta \in \mathbb{N}_0^n$
so that $x^\alpha \succ_{lex} x^\beta$ if the left-most non-zero component of the difference
$\alpha - \beta \in \mathbb{N}_0^n$ is positive.

\begin{re}
  \label{lex_re}
  Also note that the lexicographic order depends on how the underlying
  indeterminates $x_1, x_2, \ldots, x_n$ are ordered. In general, there are $n!$ ways
  to order $n$ indeterminates and each of these orders has its respective
  lexicographic order. We will only assume the standard order where $x_1 > x_2 >
  \cdots > x_n$, or the alphabetical order where $x > y > z$.
\end{re}

\begin{e}
  \label{lex_e}
  ~\begin{enumerate}[label=(\roman*)]
  \item Let $xy^2z^3$ and $xy^3$ be monomials in $\mathcal{M}\!\left( x, y, z
    \right)$. Then $xy^3 \succ_{lex} xy^2z^3$ since there is $i = 2$ and $j = 1$
    such that $\alpha_j = \beta_j$ and $\alpha_i > \beta_i$, where $\alpha = (1, 3, 0)$ and $\beta = (1, 2,
    3)$. Also, the left-most non-zero component of the difference $\beta - \alpha =
    \left( 0, 1, -3 \right)$ is positive.
  \item Let $x, y, z$ be monomials in $\mathcal{M}\!\left( x, y, z \right)$.
    Then considering remark \ref{lex_re} and example (i), we get $x \succ_{lex} y
    \succ_{lex} z$.
  \item In the lexicographic order, note that a monomial that contains the most
    significant indeterminate (as regards the underlying order) is greater than
    any other monomial that does not contain such an indeterminate. For example,
    if $x$ and $y^3z^2$ are monomials in $\mathcal{M}\!\left( x, y, z \right)$,
    then $x \succ_{lex} y^3z^2$. The reasoning is the same as in (i) and (ii).
  \end{enumerate}
\end{e}

The intuitive outlook on the lexicographic order is that it looks for the most
significant indeterminate that appears in one of the monomials and then gives
preference to the monomial in which this indeterminate has greater power.

\begin{pr}
  \label{lex_pr}
  The lexicographic order $\succeq_{lex}$ on $\mathcal{M}$ is a monomial order.
\end{pr}

\begin{p}
  Following the definition of the lexicographic order and the fact that the
  regular numerical order on $\mathbb{N}_0$ is a linear order, it is
  straightforward to show that for any monomials $x^{\alpha}, x^\beta, x^\gamma \in
  \mathcal{M}\!\left( x_1, \ldots, x_n \right)$ and $\alpha, \beta, \gamma \in \mathbb{N}_0^n$,
  the following conditions hold:
  \begin{description}
  \item[(transitivity)] if $x^\alpha \succeq_{lex} x^\beta$ and $x^\beta \succeq_{lex} x^\gamma$, then $x^\alpha
    \succeq_{lex} x^\gamma$;
  \item[(antisymmetry)] if $x^\alpha \succeq_{lex} x^\beta$ and $x^\alpha \preceq_{lex} x^\beta$, then
    $x^\alpha = x^\beta$; and
  \item[(connexity)] either $x^\alpha \succeq_{lex} x^\beta$ or $x^\alpha \preceq_{lex} x^\beta$.
  \end{description}
  These properties show that $\succeq_{lex}$ is a linear order on $\mathcal{M}$.

  Let us prove the property of respecting multiplication explicitly. If $x^\alpha
  \succeq_{lex} x^\beta$, then either $\alpha = \beta$, or there is $1 \le i \le n$ such that $\alpha_i -
  \beta_i > 0$ with $\alpha_j = \beta_j$ for $1 \le j < i$. Also, $x^\alpha \cdot x^\gamma = x^{\alpha + \gamma}$ and
  $x^\beta \cdot x^\gamma = x^{\beta + \gamma}$. Comparing the results gives us $\left( \alpha + \gamma \right)
  - \left( \beta + \gamma \right) = \alpha - \beta$ and we see that $\alpha_i - \beta_i > 0$ with $\alpha_j =
  \beta_j$ for $1 \le j < i$ again; or if $\alpha = \beta$, then $\left( \alpha + \gamma \right) = \left(
    \beta + \gamma \right)$. This shows that also $x^{\alpha+\gamma} \succeq_{lex} x^{\beta+\gamma}$.

  The last part to prove is to show that $\succeq_{lex}$ is also noetherian, i.e a
  well-order. We will prove this by the following contradiction:

  By lemma \ref{order_lm}, if $\succeq_{lex}$ is not a well-order, then there is a
  strictly decreasing sequence \[\mathlarger{x^{\alpha_{(1)}} \succ_{lex} x^{\alpha_{(2)}}
      \succ_{lex} \cdots}\] of elements in $\mathcal{M}\!\left( x_1, \ldots, x_n \right)$,
  where each $\alpha_{(i)} = \left( \alpha_1, \ldots, \alpha_n \right) \in \mathbb{N}_0^n$. By the
  definition of $\succeq_{lex}$, we also know that there exists a $j$ such that all
  the first components of the $n$-tuples $\alpha_{(k)}$ with $k \ge j$ are equal.
  Continuing further, there is an $l \ge j$ such that all the second components of
  the $n$-tuples $\alpha_{(m)}$ with $m \ge l$ are all equal. We see that there must be
  a $p \ge l$, for which the whole $n$-tuples $\alpha_{(p)} = \alpha_{(p+1)} = \cdots$ are all
  equal. This means that the sequence is not strictly decreasing, which
  contradicts the lemma.
\end{p}

\begin{df}[Reverse Colexicographic Order]
  \sloppy Let $x^\alpha, x^\beta \in \mathcal{M}\!\left( x_1, \ldots, x_n \right)$ be monomials.
  We say $x^\alpha \succeq_{rclex} x^\beta$ if $\alpha = \beta$ or if there is $1 \le i \le n$ such that
  $\alpha_j = \beta_j$ for $i < j \le n$ and $\alpha_i < \beta_i$.
\end{df}

Observe that $\succ_{rclex}$ compares the exponent $n$-tuples $\alpha, \beta \in
\mathbb{N}_0^n$ so that $x^\alpha \succ_{rclex} x^\beta$ if the right-most non-zero component
of the difference $\alpha - \beta \in \mathbb{N}_0^n$ is negative. Remark \ref{lex_re} also
applies.

\begin{e}
  \label{rclex_e}
  ~\begin{enumerate}[label=(\roman*)]
  \item Let $xy^2z^3$ and $xy^3$ be monomials in $\mathcal{M}\!\left( x, y, z
    \right)$. Then $xy^3 \succ_{rclex} xy^2z^3$ as well as in example \ref{lex_e}
    (i), but for a different reason. There is $i = 3$ such that $\alpha_i < \beta_i$,
    where $\alpha = (1, 3, 0)$ and $\beta = (1, 2, 3)$. Also, the right-most non-zero
    component of the difference $\beta - \alpha = \left( 0, 1, -3 \right)$ is negative.
  \item The lexicographic order coincides with the reverse colexicographic order
    for monomials in one and two indeterminates. These orders may differ for
    monomials in three and more variables, as shown by the following example:
    let $xz$ and $y^2$ be monomials in $\mathcal{M}\!\left( x, y, z \right)$.
    Then $xz \succ_{lex} y^2$, as explained in example \ref{lex_e} (i), but $y^2
    \succ_{rclex} xz$, as explained in example (i).
  \end{enumerate}
\end{e}

The intuitive outlook on the reverse colexicographic order is that it looks for
the least significant indeterminate that appears in one of the monomials and
then gives preference to the monomial in which this indeterminate has lesser
power. It can be thought of as a double reversal of the lexicographic order ---
we first reverse the underlying order of the indeterminates and then their
powers.

Equivalently to the lexicographic order, it is straightforward to show that the
reverse colexicographic order is a linear order as well. However, it is not a
well-order since it is possible to define the following strictly decreasing
sequence \[x_1x_2 \succ_{rclex} x_1x_2^2 \succ_{rclex} x_1x_2^3 \succ_{rclex} \cdots\] of
monomials in $\mathcal{M}\!\left( x_1, x_2 \right)$. In this sequence, let $x^\alpha
= x^{(1,n)}$ and $x^\beta = x^{(1,n+1)}$ for $n \in \mathbb{N}_{>0}$. We see that it
is always the case that $x^\alpha \succ_{rclex} x^\beta$ since $\alpha_1 = \beta_1$ and $\alpha_2 < \beta_2$,
and we get a strictly decreasing sequence. Hence, by lemma \ref{order_lm},
$\succeq_{rclex}$ is not a well-order and by definition \ref{monomial_order_df},
$\succeq_{rclex}$ cannot be a monomial order either. For this reason, we will not use
it to order monomials on its own, but we will use it as a ``sub-order'' in the
definition of the next order, which will be a monomial order.

Examples \ref{lex_e} and \ref{rclex_e} show that the lexicographic and reverse
colexicographic orders do not take into consideration the total degree of
monomials. Later in our work, we will see that in certain cases, it is desirable
to order the monomials in a polynomial according to their total degree. Let us
therefore introduce the following order, which allows for the total degree.

\begin{df}[Graded Reverse Lexicographic Order]
  \sloppy Let $x^\alpha, x^\beta \in \mathcal{M}\!\left( x_1, \ldots, x_n \right)$ be monomials.
  We say $x^\alpha \succeq_{grlex} x^\beta$ if $\lvert x^\alpha \rvert > \lvert x^\beta \rvert$, or
  $\lvert x^\alpha \rvert = \lvert x^\beta \rvert$ and $x^\alpha \succeq_{rclex} x^\beta$.
\end{df}

Notice that despite its name, the graded reverse lexicographic order actually
makes use of the reverse colexicographic order. There is a general consensus on
such a name, so we will follow it.

\begin{e}
  ~\begin{enumerate}[label=(\roman*)]
  \item Let $x, y^2, xz \in \mathcal{M}\!\left( x, y \right)$ be monomials. Then
    $y^2 \succeq_{grlex} x$ since $\lvert y^2 \rvert = 2 > \lvert x \rvert = 1$; and
    $y^2 \succeq_{grlex} xz$ since $\lvert xz \rvert = \lvert y^2 \rvert$ and $y^2
    \succeq_{rclex} xz$.
  \item Let $x, y, z \in \mathcal{M}\!\left( x, y z \right)$ be monomials. Then $x
    \succeq_{grlex} y \succeq_{grlex} z$ since $\lvert x \rvert = \lvert y \rvert = \lvert z
    \rvert$ and $x \succeq_{rclex} y \succeq_{rclex} z$.
  \end{enumerate}
\end{e}

\begin{pr}
  The graded reverse lexicographic order $\succeq_{grlex}$ on $\mathcal{M}$ is a
  monomial order.
\end{pr}

\begin{p}
  Since $\succeq_{grlex}$ first uses the usual well-order order on the total degree of
  monomials $\lvert x^\alpha \rvert \in \mathbb{N}_0$ and when $\lvert x^\alpha \rvert =
  \lvert x^\beta \rvert$, it decides ties using the reverse colexicographic order
  (which is a linear order), grlex is also linear.

  It is also straightforward to show that $\succeq_{grlex}$ is a well-order since we
  consider only the strict part $\succ_{grlex}$, which is solely the well-order on
  $\lvert x^\alpha \rvert \in \mathbb{N}_0$.

  In order to show that the property of respecting multiplication holds,
  consider the monomials $x^\alpha, x^\beta, x^\gamma \in \mathcal{M}\!\left( x_1, \ldots, x_n
  \right)$ with the $n$-tuples $\alpha, \beta, \gamma \in \mathbb{N}_0^n$. Also, $x^\alpha \cdot x^\gamma =
  x^{\alpha+\gamma}$ and $x^\beta \cdot x^\gamma = x^{\alpha+\gamma}$. Assume $x^\alpha \succeq_{grles} x^\beta$. If $\lvert x^\alpha
  \rvert > \lvert x^\beta \rvert$, then $x^{\alpha+\gamma} \succ_{grlex} x^{\beta+\gamma}$ since $\lvert
  x^{\alpha+\gamma} \rvert = \lvert x^\alpha \rvert + \lvert x^\gamma \rvert > \lvert x^\beta \rvert +
  \lvert x^\gamma \rvert = \lvert x^{\beta+\gamma} \rvert$. Also, if $\lvert x^\alpha \rvert =
  \lvert x^\beta \rvert$, we get $\lvert x^{\alpha+\gamma} \rvert = \lvert x^{\beta+\gamma} \rvert$ by
  the same argument as above and we use the reverse colexicographic order. So if
  $\lvert x^\alpha\rvert = \lvert x^\beta \rvert$, then $x^\alpha \succeq_{rclex} x^\beta$ (since we
  have assumed that $x^\alpha \succeq_{grlex} x^\beta$\big), which means that either $\alpha = \beta$,
  or there is $1 \le i \le n$ such that $\alpha_i - \beta_i < 0$ with $\alpha_j = \beta_j$ for $i < j
  \le n$. As in the proof of proposition \ref{lex_pr}, comparing the results gives
  us $\left( \alpha + \gamma \right) - \left( \beta + \gamma \right) = \alpha - \beta$ and we see that $\alpha_i
  - \beta_i < 0$ with $\alpha_j = \beta_j$ for $i < j \le n$ again; or if $\alpha = \beta$, then $\left(
    \alpha + \gamma \right) = \left( \beta + \gamma \right)$. This shows that $x^{\alpha+\gamma} \succeq_{grlex}
  x^{\beta+\gamma}$ and completes the proof.
\end{p}
